package sample.xiaosong.greedyalgorithms;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 一个数据流中，随时可以取得中位数
 * 意义在于可以随时增加数组个数，可以自己完成调整
 */
public class MedianQuick {
    // 大根队列，实际上存的是小分区数字
    public PriorityQueue<Integer> maxQueue = new PriorityQueue<>(new MaxIntegerComparator());
    // 小根队列，实际上存的是大分区数字
    public PriorityQueue<Integer> minQueue = new PriorityQueue<>(new MinIntegerComparator());

    // 一个队列比另一个队列多两个数字时，自动取出第一个数字加入另一个队列
    private void modifyTwoHeapsSize() {
        if (this.maxQueue.size() == this.minQueue.size() + 2) {
            this.minQueue.add(this.maxQueue.poll());
        }
        if (this.minQueue.size() == this.maxQueue.size() + 2) {
            this.maxQueue.add(this.minQueue.poll());
        }
    }

    // 增加一个新的数字
    public void addNumber(Integer number) {
        if (this.maxQueue.isEmpty() || number <= this.maxQueue.peek()) {
            this.maxQueue.add(number);
        } else {
            this.minQueue.add(number);
        }
        modifyTwoHeapsSize();
    }

    // 获取中位数
    public Integer getMedian() {
        Integer minSize = this.minQueue.size();
        Integer maxSize = this.maxQueue.size();
        if (maxSize + minSize == 0) {
            return null;
        }
        Integer minHead = this.minQueue.peek() == null ? 0 : this.minQueue.peek();
        Integer maxHead = this.maxQueue.peek() == null ? 0 : this.maxQueue.peek();
        // 判断数组个数是否是偶数
        if (((minSize + maxSize) & 1) == 0) {
            return (minHead + maxHead) / 2;
        }
        return minSize > maxSize ? minHead : maxHead;
    }


    // for test
    public static int[] getRandomArray(int maxLen, int maxValue) {
        int[] res = new int[(int) (Math.random() * maxLen) + 1];
        for (int i = 0; i != res.length; i++) {
            res[i] = (int) (Math.random() * maxValue);
        }
        return res;
    }

    // for test, this method is ineffective but absolutely right
    public static int getMedianOfArray(int[] arr) {
        int[] newArr = Arrays.copyOf(arr, arr.length);
        Arrays.sort(newArr);
        int mid = (newArr.length - 1) / 2;
        if ((newArr.length & 1) == 0) {
            return (newArr[mid] + newArr[mid + 1]) / 2;
        } else {
            return newArr[mid];
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        boolean err = false;
        int testTimes = 200000;
        for (int i = 0; i != testTimes; i++) {
            int len = 30;
            int maxValue = 1000;
            int[] arr = getRandomArray(len, maxValue);
            MedianQuick medianQuick = new MedianQuick();
            for (int j = 0; j != arr.length; j++) {
                medianQuick.addNumber(arr[j]);
            }
            if (medianQuick.getMedian() != getMedianOfArray(arr)) {
                err = true;
                printArray(arr);
                break;
            }
        }
        System.out.println(err ? "Oops..what a fuck!" : "today is a beautiful day^_^");

        MedianQuick medianQuick = new MedianQuick();
        int[] arr = new int[]{7, 5, 4, 9, 8, 12};
        for (int i: arr) {
            medianQuick.addNumber(i);
        }
        System.out.println(medianQuick.getMedian());
    }

    public static class MinIntegerComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            if (o2 < o1) {
                return 1;
            } else {
                return -1;
            }
        }
    }

    public static class MaxIntegerComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            if (o2 > o1) {
                return 1;
            } else {
                return -1;
            }
        }
    }
}
